package org.lql.algo.codecrush.week007;

/**
 * @author: liangqinglong
 * @date: 2025-08-18 23:17
 * @description: 154. 寻找旋转排序数组中的最小值 II <a href="https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array-ii/description/">...</a>
 **/
public class FindMinII {

	public int findMin(int[] nums) {
		int left = 0;
		int right = nums.length - 1;
		while (left < right) {
			int mid = left + (right - left) / 2;
			// 原数组：[a[0], a[1], a[2], ..., a[n-1]]
			// x次旋转后的数组：[a[n-x],a[n-x+1]..,a[0],a[1],a[2]...,a[n-x-1]]
			// 是两个有序数组相连
			// 以数组一端作为比较点，进行二分查找
			if (nums[mid] > nums[right]) {
				left = mid + 1;
			} else if (nums[mid] < nums[right]) {
				right = mid;
			} else {
				right--;
			}
		}
		return nums[left];
	}

	public static void main(String[] args) {
		FindMinII findMinII = new FindMinII();
		System.out.println(findMinII.findMin(new int[]{1, 3, 5}));
		System.out.println(findMinII.findMin(new int[]{2, 2, 2, 0, 1}));
	}
}
